package nowCoder;

import java.util.*;

public class HJ16 {
    /*
10 5
8 2 0
4 5 1
3 5 1
4 3 0
5 2 0

11 5
8 2 0
4 5 1
3 5 1
4 3 0
5 2 0

5 5
2 3 5
2 3 5
1 3 0
1 2 0
1 1 0

10 5
3 5 0
4 2 0
3 5 2
3 4 2
6 4 0

200 10
50 1 0
40 4 0
30 5 1
40 5 1
20 5 0
50 4 5
40 4 0
32 2 0
41 3 0
40 3 5
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt(); // 总钱数
        int goods = in.nextInt(); // 商品个数
        Item[] gi = new Item[goods+1];
        for (int i = 1; i <= goods; i++) {
            Item item = new Item();
            item.price = in.nextInt();
            item.my = in.nextInt() * item.price;
            item.zi = in.nextInt();
            gi[i]=item;
        }
        List<Item> list = new ArrayList<>();
        for (int i = 0; i < goods; i++) {
            Item item = gi[i+1];
            if (item.zi == 0) list.add(item);
            else gi[item.zi].set(item);
        }
        int[][] myd = new int[money + 1][list.size() +1];
        for (int m = 1; m <= money; m++) {
            for (int g = 1; g <= list.size(); g++) {
                Item item = list.get(g-1);
                myd[m][g] = myd[m][g-1];
                if (m < item.price) continue;
                myd[m][g] = Math.max(myd[m][g], myd[m-item.price][g-1] + item.my);
                if (item.a != null && m >= item.price + item.a.price)
                    myd[m][g] = Math.max(myd[m][g], myd[m-item.price-item.a.price][g-1] + item.my+item.a.my);
                if (item.b != null && m >= item.price + item.b.price)
                    myd[m][g] = Math.max(myd[m][g], myd[m-item.price-item.b.price][g-1] + item.my+item.b.my);
                if (item.a != null && item.b != null && m >= item.price + item.a.price + item.b.price)
                    myd[m][g] = Math.max(myd[m][g], myd[m-item.price-item.a.price-item.b.price][g-1] + item.my+item.a.my+item.b.my);
            }
        }
        System.out.println(list);
        for (int i = 0; i <= money; i++) {
            System.out.println(Arrays.toString(myd[i]));
        }
        System.out.print(myd[money][list.size()]);
    }
}
class Item{
    int price;
    int my;
    int zi;
    Item a;
    Item b;
    public void set(Item x){
        if (a == null) a = x;
        else b = x;
    }

    @Override
    public String toString() {
        return "Item{" +
                "price=" + price +
                ", my=" + my +
                ", zi=" + zi +
                ", a=" + a +
                ", b=" + b +
                '}';
    }
}